package com.maltys.greedy;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author Administrator
 * @link <a href="https://leetcode.cn/problems/queue-reconstruction-by-height/">...</a>
 */
public class ReconstructQueueByHeight {
    public static void main(String[] args) {
        ReconstructQueueByHeight height = new ReconstructQueueByHeight();
        int[][] res = height.reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}});
        for (int[] re : res) {
            System.out.println(Arrays.toString(re));
        }
    }

    /**
     * 按照身高倒排，然后插入排序
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            // 大于等于当前身高的前面的人的个数
            queue.add(people[i][1], people[i]);
        }
        return queue.toArray(new int[people.length][]);
    }

    private void swap(int[][] array, int i, int j) {
        int[] temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

